

		INTERSECTII DE DREPTUNGHIURI
	       ------------------------------

	In satul Valea lui Liman a ajuns legea reformei agrare. Fiecare satean s-a repezit sa caute in
sertare sau poduri documente vechi, ramase de la batrani, pentru a cere cat mai mult pamant.
	Comisia de distribuire a pamantului este formata din primar si ... atat. Caci sunt putini
oameni ramasi in sat, si de unde sa aleaga alti membri?...
	Primarul a cerut satenilor sa-si prezinte in scris pretentiile. Dupa 2 zile, cererile ta-
ranilor erau asezate vraf pe biroul primarului. Fiecare familie a cerut un sungur lot, dreptun-
ghiular. Toate loturile au laturile paralele intre ele. Primarul a primit de la fiecare satean co-
ordonatele colturilor opuse ale lotului cerut. Oameni intelepti, satenii au evitat sa includa in
loturi zonele mlastinoase, acestea fiind portinui de teren inconjurate complet de loturi, nesolici-
tate de nimeni.
	Fapt interesant, desi pot exista zone revendicate de mai multi sateni (si care apartin deci
de mai multe loturi), singurele zone agricloe ale satului nerevendicate sunt cele mlastinoase.

	Scrieti un program care determina cate astfel de portiuni mlastinoase se afla in Valea
lui Liman.

INTRARE:
	Datele de intrare se gasesc intr-un fisier al carui nume se citeste de la tastatura. Struc-
tura unui fisier de date este:
n		- nr. de loturi
a1 b1 c1 d1	-(a1,b1) si (c1,d1) sunt coordonatele colturilor opuse ale lotului din prima cerere
....
an bn cn dn

	Toate coordonatele sunt numere reale pozitive, iar laturile loturilor sunt paralele cu
axele de coordonate.
	In plus, daca (x1,y1) si (z1,u1) sunt 2 varfuri oarecare din 2 loturi diferite, atunci
x1<>z1 si y1<>u1.

IESIRE:
	Se scrie pe ecran un singur numar intreg k, reprezentand nr. zonelor mlastinoase din zona
satului.

EXEMPLU:
INTRARE:		IESIRE:
5			2
0.0 0.0 10.1 1.1
0.2 2.0 10.0 3.2
10.4 5.3 0.1 4.3
0.3 0.1 1.0 5.0
10.2 5.1 9.6 0.3

SOLUTIE
--------

	Rezolvarea problemei porneste de la impartirea terenului in "zone elementare", zone care
nu se intersecteaza cu nici un dreptunghi.
	Se observa ca aceste zone formeaza o matrice patratica de ordinul 2n-1. Elementul A{i,j]
al matricii A va fi egal cu 1 daca si numai daca exista cel putin un dreptunghi care sa contina
zona respectiva.
	Avand aceasta matrice, se aplica banalul algoritm de FILL si problema este rezolvata.
	Cum construim aceasta matrice?
	Introducem toate coordonatele x ale dreptunghiurilor in vectorul X si toate coordonatele
Y ale dreptunghiurilor in vectorul Y. Sortam crescator acesti doi vectori. Pentru exemplul din
enunt acesti vectori vor fi:
X = (0.0,0.1,0.2,0.3,1.0,9.6,10.0,10.1,10.2,10.4)
Y = (0.0,0.1,0.3,1.1,2.0,3.2,4.3,5.0,5.1,5.3)
(vectorii au fiecare cate 2n componente).
	Asa cum am mai spus, un element A[i,j] din matrice va reprezenta o zona elementara din
plan. A[i,j] are valoarea 1 daca si numai daca zona corespunzatoare este acoperita de cel putin
un dreptunghi, si 0 altfel. Zona elementara reprezentata de A[i,j] este un dreptunghi cu coor-
donatele colturilor opuse (X[i],Y[j]) si (X[i+1],Y[j+1]), i=1,..,2n-1 , j=1,..,2n-1.
	Dreptunghiurile initiale vor fi pastrate in vectorul "drept" cu elemente de tipul
record
	x1,y1,x2,y2:real;
	px1,px2,py1,py2:integer;
end;

unde:
- (x1,y1) , (x2,y2) sunt coordonatele colturilor dreptunghiului
- px1 este pozitia pe care apare x1 in vectorul X
- px2 este pozitia pe care apare x2 in vectorul X
- py1 este pozitia pe care apare y1 in vectorul Y
- py2 este pozitia pe care apare y2 in vectorul Y

	Matricea A este initializata cu 0. Pentru a marca elementele de 1 din matrice avem
2 posibilitati:
I.	Pentru fiecare element (i,j) al matricii, parcurgem toate dreptunghiurile si in caz
ca exista cel putin unul care sa contina zona (i,j), atunci atribuim elementului A[i,j] din
matrice valoarea 1.
II.	Pentru fiecare dreptunghi, marcam cu 1 toate zonele acoperite de acesta.

	Sa analizam cele 3 cazuri:
	Primul caz realizeaza (2n-1)^2 operatii, in timp ce al doilea caz realizeaza
n*D1 + n*D2 + .. + n*Dn operatii unde Di reprezinta aria dreptunghiului i. Bineinteles ca cel
de-al doilea caz este de preferat primului, deoarece dimensiunea medie a unui dreptunghi va fi
intotdeauna mai mica decat dimensiunea matricei ( (2n-1)^2 ), pe cazul mediu ea fiind chiar
mult mai mica.
	Avand matricea binara A construita, pornim din fiecare punct de valoare 0, umplem zona
respectiva cu 1, iar numarul de astfel de zone va fi numarul de mlastini cerut.

	Pentru a nu gasi mlastini si in exteriorul loturilor, se bordeaza matricea cu linia 0,
linia 2n, coloana 0 si coloana 2n, ale caror elemente vor fi 0. Apoi se aplica algoritmul de
umplere pornind din punctul (0,0) al matricii. Dupa acest "fill exterior", se va aplica al-
goritmul FILL pentru fiecare zona de 0 din matrice si numarand aceste zone, obtinem rezultatul
problemei. 